package io.github.dunwu.algorithm.trie;

import org.junit.jupiter.api.Assertions;

/**
 * @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
 * @see <a href="https://leetcode-cn.com/problems/word-search/">79. 单词搜索</a>
 * @since 2020-07-04
 */
public class 单词搜索 {

    public static void main(String[] args) {
        char[][] board = {
            { 'A', 'B', 'C', 'E' },
            { 'S', 'F', 'C', 'S' },
            { 'A', 'D', 'E', 'E' }
        };
        单词搜索 demo = new 单词搜索();
        // Assertions.assertFalse(demo.exist(board, "ABCB"));
        Assertions.assertTrue(demo.exist(board, "SEE"));
        Assertions.assertTrue(demo.exist(board, "ABCCED"));

        char[][] board2 =
            { { 'p', 'f', 'h', 'n', 'u', 'v', 'u', 'z', 'z', 'p', 'u', 'j', 's', 't', 'p', 'i', 'v', 'o', 's', 'm', 'q',
                'l', 'c', 't', 'y', 'n', 's', 'p', 'u', 't', 'y', 'l', 'y', 'i', 'a', 'u', 'f', 'u', 't', 'f', 'j', 'n',
                'q', 'd', 'j', 'f', 'n', 'e', 'v', 'f', 't', 'o', 't', 'v', 'h', 't', 'i', 'c', 'j', 'e', 'v', 'j', 'r',
                'v', 'r', 'r', 'p', 'x', 'l' },
                { 'k', 'e', 'w', 'z', 'u', 'b', 'i', 'b', 'p', 'p', 'w', 'w', 'i', 'k', 'p', 'd', 'u', 'l', 'n', 'w',
                    'u', 's', 'r', 'd', 'j', 'o', 'x', 'b', 'd', 'w', 'o', 'p', 'a', 'l', 'o', 'w', 'o', 'x', 'x', 'd',
                    'o', 't', 'c', 'w', 'g', 'r', 'z', 'a', 'e', 'o', 'w', 'y', 'g', 'p', 'e', 's', 'd', 'd', 'v', 'i',
                    'z', 'j', 'z', 'b', 'w', 'n', 'x', 'l', 'm' },
                { 'u', 'q', 'a', 'n', 's', 'w', 't', 'm', 'x', 'v', 'q', 'o', 'r', 'r', 'u', 'i', 'x', 'o', 'n', 'a',
                    'j', 'v', 'b', 'v', 'u', 'c', 't', 'k', 'z', 'g', 'w', 't', 'x', 'z', 'i', 'r', 'x', 'e', 'd', 'x',
                    'z', 'w', 'l', 't', 'p', 'h', 'b', 'm', 'w', 'p', 'm', 'h', 'm', 'n', 'c', 'j', 'p', 'w', 'v', 'q',
                    'c', 't', 'j', 'b', 's', 't', 't', 's', 'x' },
                { 'y', 'p', 'x', 'w', 'c', 'q', 'l', 'j', 't', 'x', 'f', 'k', 'l', 'p', 'x', 'a', 'r', 'i', 'r', 'p',
                    'd', 'h', 'u', 'w', 's', 'x', 'p', 'm', 'q', 'j', 'j', 'r', 'y', 'i', 'n', 'a', 'a', 'b', 'l', 'u',
                    'y', 't', 'e', 'k', 'i', 'd', 'k', 'b', 'l', 'e', 'r', 'o', 'l', 'n', 'n', 'e', 'k', 'e', 'q', 'd',
                    'n', 'b', 'u', 'l', 'k', 'j', 'n', 'k', 'k' },
                { 'y', 'g', 'l', 't', 'l', 'x', 'b', 'q', 'h', 'd', 'c', 'l', 'w', 's', 'z', 'j', 'f', 'f', 't', 'j',
                    'v', 'w', 'w', 'y', 's', 'j', 'k', 'e', 'y', 'x', 'q', 'x', 'd', 'b', 'q', 'q', 'y', 'u', 'h', 'i',
                    'x', 'l', 'v', 'v', 'd', 'u', 'e', 'l', 'b', 'z', 'w', 'w', 'y', 't', 'x', 'q', 'e', 'h', 'w', 'd',
                    'e', 'n', 'c', 'k', 'q', 'u', 'a', 'r', 'q' },
                { 'j', 'z', 'n', 'u', 'w', 'i', 'a', 't', 'o', 'n', 'u', 'o', 'j', 't', 'm', 'e', 'q', 'e', 'j', 'z',
                    'b', 'o', 'g', 'q', 's', 'q', 'i', 'm', 's', 'z', 'd', 'c', 'y', 's', 'y', 'v', 'd', 'a', 'q', 'r',
                    'n', 'k', 'h', 'x', 'd', 't', 'd', 't', 'y', 'o', 'v', 'b', 'c', 'b', 't', 'w', 'r', 'b', 'j', 'l',
                    'b', 'o', 'n', 'b', 'i', 'o', 'y', 'n', 'q' },
                { 'o', 'h', 'e', 'z', 'o', 'd', 'c', 'i', 'i', 'y', 'i', 'x', 'v', 'l', 'b', 'w', 'e', 'y', 'p', 'f',
                    'j', 'a', 'g', 'x', 'q', 'i', 'h', 'e', 'g', 'v', 'u', 'v', 'c', 'a', 'w', 's', 'f', 'a', 'c', 'o',
                    'y', 'k', 'l', 'v', 'v', 'm', 'r', 'b', 'k', 'g', 'h', 't', 'h', 'n', 's', 'x', 'x', 'c', 'd', 'e',
                    'x', 'z', 'b', 'b', 'c', 'x', 't', 'h', 'x' },
                { 'w', 'x', 'y', 'i', 'i', 't', 'g', 'x', 'n', 'h', 'j', 't', 'q', 'f', 'c', 'g', 'x', 'b', 'd', 'b',
                    'e', 'j', 'y', 'g', 'm', 'b', 'i', 'l', 'x', 'r', 'j', 'v', 'p', 'j', 'f', 'z', 'e', 'l', 'w', 't',
                    'v', 'i', 'n', 'l', 'n', 'r', 't', 'm', 't', 'x', 'o', 'z', 'i', 'o', 'f', 'v', 'q', 'n', 'g', 'n',
                    'f', 'r', 'k', 'w', 'c', 'p', 'v', 'h', 'd' },
                { 's', 'c', 'y', 'c', 'p', 'l', 'p', 'j', 'h', 'b', 'c', 'e', 'p', 'b', 'm', 'e', 'h', 'h', 'w', 'w',
                    'q', 'l', 'd', 'h', 'v', 'z', 'k', 'k', 'v', 't', 'n', 'p', 'v', 'n', 'r', 'n', 'b', 'g', 'w', 'i',
                    'j', 'y', 'o', 'z', 'b', 'c', 'f', 'k', 'm', 'b', 'h', 'c', 'm', 'k', 'j', 'j', 'm', 'v', 't', 'h',
                    'o', 'j', 'y', 'k', 'y', 'r', 'z', 'b', 'x' },
                { 'v', 'j', 'i', 'v', 'z', 'j', 'y', 'c', 'o', 'j', 'o', 'r', 'q', 'q', 'f', 'c', 'b', 'o', 'o', 'x',
                    'i', 'x', 'l', 't', 'v', 'x', 'r', 'o', 'w', 't', 'n', 't', 'e', 'w', 'q', 'e', 'f', 'p', 'g', 'w',
                    'y', 'w', 'n', 'q', 'o', 't', 'u', 'p', 'h', 'j', 'm', 'r', 'i', 'a', 'k', 'g', 'z', 'c', 'u', 'y',
                    'x', 'i', 't', 'b', 'e', 'k', 'f', 'l', 'z' },
                { 'n', 'h', 'z', 'j', 'v', 'p', 'z', 'q', 'l', 'p', 'x', 'w', 'd', 'p', 'f', 'f', 'b', 'n', 'f', 'd',
                    'h', 'f', 'a', 'r', 'y', 'c', 'x', 'i', 'j', 'j', 'j', 'z', 'q', 'i', 'k', 'n', 'z', 'k', 'd', 'l',
                    'z', 'd', 'h', 'e', 's', 'o', 'k', 't', 'b', 'p', 'z', 'l', 'u', 'b', 'c', 'u', 'f', 'a', 'd', 'r',
                    'l', 'o', 'q', 'b', 'z', 'a', 'r', 'a', 'k' },
                { 'u', 'n', 'l', 'x', 'x', 'q', 'r', 'l', 'a', 'n', 'p', 'r', 'o', 'a', 'n', 'p', 'e', 'h', 'v', 'e',
                    'm', 'm', 'p', 'b', 'e', 't', 'c', 'e', 'k', 'c', 'r', 'g', 'q', 'e', 'g', 'n', 'w', 'x', 'a', 'y',
                    'm', 'p', 'p', 'a', 'r', 'c', 'q', 'w', 'm', 'n', 'a', 'y', 'b', 's', 'b', 'f', 'n', 'd', 'l', 'x',
                    'g', 'c', 'f', 'w', 'j', 'l', 'l', 'f', 'j' },
                { 'l', 'e', 'v', 'd', 'v', 'w', 'u', 'y', 'o', 'q', 'm', 'b', 't', 'k', 'c', 'l', 'm', 'j', 'a', 'r',
                    'u', 'x', 'x', 'x', 'e', 'v', 'i', 'q', 'i', 'n', 'b', 'u', 't', 'w', 'x', 'p', 'u', 'r', 'p', 'k',
                    'k', 'd', 'n', 'd', 'n', 'r', 'q', 'b', 'a', 'q', 't', 'v', 'p', 's', 'u', 't', 'q', 'c', 'j', 'y',
                    'r', 'k', 's', 'n', 'j', 'r', 'e', 'f', 'l' },
                { 'v', 's', 'v', 'y', 'f', 'a', 'n', 'x', 's', 'p', 'x', 'i', 'k', 'u', 'z', 'e', 'o', 'u', 'u', 's',
                    'g', 't', 'm', 'q', 'n', 'z', 'b', 'f', 'f', 'j', 'q', 'a', 'b', 'n', 'y', 'g', 'p', 'n', 'f', 'h',
                    'c', 'f', 'r', 'o', 'z', 'q', 't', 'o', 'k', 'n', 'i', 'q', 'i', 'u', 'j', 'w', 'v', 'm', 'b', 'a',
                    'v', 't', 'a', 'y', 'i', 'a', 'h', 'x', 'o' },
                { 'm', 'e', 's', 'r', 'v', 'j', 'r', 'n', 'c', 'h', 'x', 'r', 'r', 'q', 'a', 'm', 'b', 'w', 'j', 'n',
                    'z', 'k', 'l', 's', 'm', 'j', 'c', 'p', 's', 'z', 'f', 'f', 'f', 'x', 'y', 'c', 'g', 'r', 'r', 'k',
                    'a', 'q', 'e', 's', 'g', 'e', 'g', 'h', 'c', 'p', 'v', 'b', 'b', 'i', 'v', 'q', 'r', 'x', 'f', 'm',
                    'y', 'k', 'r', 'f', 'j', 'r', 'h', 's', 'j' },
                { 'a', 'e', 'j', 'q', 'i', 'd', 'x', 'm', 'j', 'g', 'q', 'b', 'b', 'r', 'e', 'l', 'o', 'u', 'f', 'n',
                    'z', 'r', 'l', 'l', 'i', 's', 'x', 'b', 'b', 'p', 'k', 'b', 't', 'w', 's', 'c', 'b', 'p', 'q', 'n',
                    'v', 'h', 'o', 'z', 'a', 's', 'k', 'p', 'n', 'p', 'c', 'o', 'i', 'q', 'c', 'q', 'i', 'z', 's', 'k',
                    'o', 'e', 'l', 'j', 'c', 'f', 'l', 'e', 'u' },
                { 'c', 'r', 's', 'l', 'h', 't', 'l', 'b', 'f', 'a', 'q', 'x', 'f', 'f', 'f', 'v', 'h', 'y', 'f', 'g',
                    's', 'r', 'w', 'w', 'f', 'f', 'b', 'k', 't', 'f', 'h', 'x', 'y', 'b', 'i', 'f', 'u', 't', 'g', 'b',
                    'w', 'x', 'y', 'b', 'e', 'e', 'y', 'l', 'e', 'f', 't', 'w', 'x', 'r', 'u', 'c', 'y', 'v', 'o', 'r',
                    'c', 'v', 'o', 'a', 'y', 'y', 'f', 's', 's' },
                { 'o', 'u', 'q', 'l', 'u', 't', 'p', 'a', 'r', 'c', 'e', 'w', 'x', 'c', 'v', 'q', 'x', 'x', 'o', 'u',
                    'o', 'g', 'x', 'j', 'w', 'x', 'i', 'v', 'f', 'c', 'p', 't', 'y', 'f', 'g', 'v', 'y', 'x', 'v', 'r',
                    'b', 'c', 'p', 'y', 'e', 'l', 'o', 'b', 'k', 'e', 'y', 'y', 'k', 'v', 'k', 'j', 'u', 'u', 'e', 'z',
                    'y', 't', 'u', 'x', 'a', 'a', 'u', 'a', 'x' },
                { 'p', 't', 'y', 't', 'i', 'y', 'y', 't', 'o', 'b', 'e', 't', 'z', 'e', 'f', 'u', 'o', 'o', 'p', 'k',
                    's', 'q', 'j', 'n', 'l', 'i', 'p', 'n', 'c', 'p', 'n', 't', 'i', 'l', 'n', 't', 'm', 'l', 'o', 'c',
                    'm', 'u', 'v', 'o', 'z', 'd', 'i', 'p', 'r', 'z', 'a', 'm', 's', 'j', 'b', 'f', 'r', 'r', 's', 't',
                    'i', 'f', 'm', 't', 't', 'b', 'm', 'f', 'm' },
                { 'a', 'h', 'b', 'x', 'f', 'p', 'w', 'i', 'z', 'l', 'b', 'b', 'l', 'p', 't', 'w', 'r', 'y', 'n', 'k',
                    'q', 'i', 's', 'y', 'x', 'n', 'r', 'y', 'b', 'y', 'n', 'e', 'h', 'o', 'b', 'o', 'd', 'x', 'y', 'e',
                    'k', 'a', 'f', 'y', 'p', 'y', 'u', 'i', 'y', 'k', 's', 'p', 's', 'n', 'p', 'r', 'a', 'g', 'q', 'e',
                    'g', 'd', 'i', 'n', 't', 'l', 'e', 'y', 'i' },
                { 'c', 'c', 'u', 'c', 'i', 's', 'u', 'i', 'n', 'c', 'h', 'x', 'v', 'y', 'r', 'i', 'n', 'j', 'k', 't',
                    'z', 'o', 'b', 'e', 'y', 'q', 'x', 'j', 'u', 'v', 't', 'x', 'x', 'o', 'b', 'h', 'g', 'v', 'q', 'v',
                    'y', 'x', 'u', 'v', 'x', 'm', 'f', 'k', 'v', 'p', 'f', 'w', 'g', 'g', 'a', 'e', 'w', 'z', 'o', 't',
                    'u', 'h', 'q', 't', 'x', 'r', 'b', 'e', 'n' },
                { 't', 'b', 'n', 's', 'w', 'k', 'p', 'i', 'p', 'z', 'f', 'g', 'g', 'b', 'm', 'm', 'd', 't', 'k', 'c',
                    'h', 'd', 'w', 'q', 't', 'r', 'q', 'n', 'u', 'w', 'c', 'n', 'x', 'p', 'h', 't', 'z', 'w', 'd', 'q',
                    'x', 'i', 'w', 'd', 'j', 'j', 'r', 'm', 'c', 'c', 'o', 'l', 'f', 'm', 'd', 'b', 'g', 't', 'q', 'a',
                    'p', 's', 'q', 'p', 'j', 'x', 'i', 'k', 'w' },
                { 'm', 'a', 't', 'u', 'w', 'z', 'g', 'h', 'q', 's', 'l', 'u', 'j', 'y', 'c', 'v', 'e', 'f', 'b', 'z',
                    'v', 'e', 'r', 'n', 'u', 'g', 'y', 'r', 'q', 'i', 'n', 'e', 'k', 'j', 'z', 'i', 'i', 'h', 's', 'a',
                    'z', 'd', 'v', 'i', 'e', 'x', 'g', 'i', 'c', 'j', 'j', 'z', 'n', 'a', 'o', 'h', 'i', 'm', 'z', 'z',
                    'w', 'o', 'd', 'g', 'x', 'e', 'q', 'h', 'l' },
                { 'i', 'k', 'n', 'o', 'f', 'v', 's', 'e', 'd', 'c', 'i', 'n', 'n', 'j', 'a', 'o', 'x', 'k', 'y', 'j',
                    'l', 'x', 'f', 'b', 'd', 'n', 'b', 'j', 'd', 'i', 'x', 'o', 's', 'k', 'c', 'z', 'h', 'w', 'f', 'l',
                    'a', 'p', 'a', 'n', 'y', 'c', 'd', 'v', 'm', 'c', 'g', 'z', 'b', 'l', 'b', 'g', 'a', 'c', 'q', 'g',
                    'k', 'n', 'u', 'f', 'x', 'y', 'g', 'g', 'u' },
                { 'o', 'r', 'u', 'd', 'r', 'j', 'c', 'u', 'n', 'z', 'i', 'r', 'g', 'i', 'u', 't', 'j', 'b', 'u', 'l',
                    't', 'c', 'x', 'g', 'w', 'e', 'f', 'u', 'l', 'l', 'q', 'z', 'f', 'm', 'e', 'w', 'v', 'g', 's', 'k',
                    'g', 'b', 'd', 'o', 'j', 'y', 'h', 'u', 'z', 'd', 'f', 's', 'f', 'e', 'a', 'b', 'j', 'f', 'x', 'u',
                    's', 'p', 'v', 'x', 'b', 'z', 'w', 'z', 'i' },
                { 'o', 'l', 'q', 'r', 'p', 'e', 'c', 'n', 'n', 'w', 'o', 'r', 'd', 'g', 'w', 'i', 'i', 'a', 'r', 'p',
                    'z', 'n', 'h', 'p', 'k', 'h', 's', 'l', 'd', 't', 'v', 't', 'f', 'n', 'l', 'u', 'r', 'n', 'j', 'h',
                    'm', 'x', 'y', 'p', 'f', 'u', 'z', 'n', 'w', 's', 'c', 'w', 'h', 'l', 'n', 'r', 's', 'h', 'f', 'v',
                    'b', 'a', 'p', 'i', 'o', 'c', 'c', 'h', 'p' },
                { 'n', 'o', 'd', 'm', 'o', 'v', 'r', 'l', 'u', 'g', 'h', 'n', 'i', 'f', 'u', 't', 's', 'o', 'o', 'a',
                    't', 'j', 'd', 'v', 'a', 'l', 'l', 'c', 'p', 't', 'u', 'c', 'j', 'z', 'o', 'y', 'u', 'h', 'j', 'p',
                    'n', 's', 'e', 'x', 'y', 'y', 's', 's', 'o', 'g', 'u', 'j', 's', 'x', 'f', 'u', 'i', 'q', 'x', 'x',
                    'l', 't', 'b', 'x', 's', 'r', 'x', 'n', 'y' },
                { 'i', 'e', 'n', 'a', 'i', 'm', 'a', 'i', 'h', 't', 'x', 'n', 'n', 'g', 'h', 'l', 'l', 'c', 'v', 'e',
                    'b', 'v', 'r', 'w', 'w', 'o', 'o', 'q', 'l', 'd', 'q', 't', 'j', 'e', 'w', 'r', 's', 'w', 'a', 'z',
                    'r', 'z', 'p', 'f', 'f', 'w', 's', 't', 'a', 'p', 'x', 'b', 'k', 'q', 'x', 'j', 'f', 'o', 'z', 's',
                    't', 'p', 'o', 'd', 'v', 'k', 'w', 'o', 'g' },
                { 'y', 'p', 'a', 'x', 'e', 'f', 'd', 'd', 'z', 'y', 'd', 'o', 'x', 'h', 'b', 'n', 'g', 'k', 'u', 'w',
                    'j', 'n', 'q', 'y', 'b', 'v', 'w', 'l', 'r', 'k', 't', 's', 'b', 't', 'p', 'g', 'a', 'u', 'l', 'b',
                    's', 'q', 'q', 'p', 'x', 'r', 'd', 'e', 'd', 'x', 'a', 'm', 'm', 's', 'm', 'n', 'n', 'i', 'a', 'h',
                    'u', 'w', 'b', 'w', 'p', 'q', 'e', 's', 'l' },
                { 'r', 't', 'd', 'h', 'l', 'v', 'f', 'e', 'a', 'l', 'h', 'z', 'l', 'v', 'm', 'g', 'i', 'b', 'v', 's',
                    'c', 'e', 'n', 'y', 'f', 'l', 'p', 'w', 'p', 'h', 'j', 'g', 'd', 'o', 'n', 'o', 'j', 'u', 'v', 'l',
                    'f', 'c', 'l', 't', 'y', 'x', 'z', 'i', 'y', 'u', 'a', 'c', 'z', 'p', 'a', 'g', 'a', 'q', 'c', 'r',
                    'z', 'l', 'z', 'c', 'c', 'p', 't', 'l', 'j' },
                { 'o', 'x', 'p', 's', 'k', 'k', 's', 'h', 'j', 'a', 'h', 'f', 'b', 'k', 'g', 's', 'm', 'n', 't', 'c',
                    'r', 'k', 'c', 'f', 'k', 'g', 'h', 'z', 'z', 'u', 'k', 'n', 't', 'z', 'g', 'd', 'l', 'y', 'm', 'w',
                    'z', 'w', 'c', 'c', 'i', 'k', 'w', 'u', 'z', 'p', 'x', 'r', 'a', 'b', 'w', 'm', 'h', 'f', 'l', 'h',
                    'z', 'x', 'w', 'v', 'x', 'c', 'y', 'k', 'd' },
                { 'n', 'h', 'e', 'j', 'j', 'i', 'r', 'v', 'e', 'l', 'v', 'u', 'k', 'm', 'w', 'n', 'k', 'i', 'v', 'r',
                    'v', 'e', 's', 's', 'a', 'n', 'r', 'f', 'o', 'c', 'i', 'b', 'j', 'm', 'k', 'u', 'u', 'd', 'p', 'y',
                    'o', 'm', 's', 'b', 'y', 'o', 'o', 'k', 'y', 'l', 'd', 't', 'r', 'w', 'm', 'u', 'j', 'f', 'z', 'x',
                    'h', 'j', 'y', 's', 'v', 'k', 'o', 'p', 'n' },
                { 'e', 'p', 'e', 's', 'k', 'f', 't', 'a', 'v', 'd', 'z', 'j', 'h', 's', 'a', 'f', 'g', 'w', 'o', 'm',
                    'v', 'o', 'v', 'e', 'o', 'o', 'b', 'z', 'e', 's', 'm', 'i', 'i', 's', 'd', 's', 'x', 'w', 'u', 'v',
                    'z', 't', 'e', 'i', 'o', 'g', 'n', 'u', 'd', 'e', 'i', 'y', 's', 'g', 'f', 'g', 'w', 'g', 'h', 'a',
                    'b', 'w', 'l', 'j', 'o', 'o', 'd', 'm', 'k' },
                { 'z', 'h', 'j', 't', 'n', 'u', 'h', 't', 'j', 'd', 'w', 'n', 'o', 'x', 'h', 'u', 'c', 'q', 'q', 'k',
                    'x', 'q', 'n', 't', 'b', 'w', 'k', 'p', 'b', 'w', 'z', 'b', 'f', 'l', 'w', 'u', 'h', 'f', 'n', 'q',
                    'i', 'k', 'g', 'w', 'j', 'p', 'q', 'n', 'f', 'g', 'x', 'f', 'z', 'l', 'a', 'a', 'j', 'k', 's', 'n',
                    'i', 't', 'q', 'p', 'e', 'o', 'j', 'n', 't' },
                { 'x', 'g', 'b', 'j', 'm', 'a', 'u', 'b', 'q', 'h', 'j', 'z', 'e', 'q', 'y', 'r', 'q', 'a', 'd', 'b',
                    'u', 's', 'l', 'o', 'i', 'b', 'u', 'w', 'k', 'i', 'r', 'j', 'o', 's', 'u', 'c', 's', 'o', 'f', 'l',
                    'v', 'o', 'k', 'c', 'e', 'k', 't', 'x', 'm', 'y', 'a', 'h', 'q', 'l', 'v', 'a', 'm', 'r', 'y', 'z',
                    'b', 'p', 'k', 'p', 'i', 'f', 't', 'c', 'v' },
                { 'z', 'n', 'r', 'p', 'z', 'v', 'w', 'j', 'q', 't', 'y', 'p', 'v', 'f', 'h', 'g', 'c', 'i', 'v', 't',
                    'g', 'w', 'x', 'w', 'g', 'o', 'g', 'n', 'i', 'i', 'j', 'j', 'w', 'c', 'y', 'x', 'x', 'w', 'h', 'p',
                    'r', 'h', 'e', 'm', 'm', 'm', 't', 'q', 'u', 'q', 'l', 'c', 'm', 'i', 'y', 's', 'x', 'e', 'i', 'f',
                    'p', 'r', 'q', 'n', 'v', 'o', 'k', 'u', 'n' },
                { 'r', 'j', 'e', 'y', 'o', 'r', 'm', 'c', 'm', 'e', 'y', 'e', 'q', 'a', 'q', 'a', 'b', 'k', 'x', 'h',
                    's', 'e', 'w', 'l', 'u', 'j', 'g', 'l', 'u', 'a', 'y', 'n', 'k', 'e', 'o', 'a', 'v', 'c', 'e', 'j',
                    'h', 'c', 'n', 'z', 'e', 'd', 'z', 'h', 'q', 'x', 'p', 'i', 'd', 'n', 'w', 'a', 'z', 'c', 'l', 't',
                    'f', 'l', 'i', 'r', 'p', 'y', 'r', 'n', 'b' },
                { 'x', 'w', 'k', 'z', 'm', 'j', 'f', 'r', 'k', 'n', 'h', 'j', 'e', 's', 'n', 'r', 'o', 'p', 'q', 'q',
                    'a', 'l', 'v', 'n', 'u', 'o', 'e', 'u', 'f', 'r', 'x', 'c', 'q', 'h', 'd', 'c', 's', 'l', 't', 'd',
                    'y', 'b', 'm', 'c', 't', 'b', 'v', 'j', 'q', 'm', 'z', 's', 'x', 'x', 'h', 't', 'l', 'm', 'q', 't',
                    'd', 'n', 'x', 'v', 'x', 'd', 'x', 'r', 'o' },
                { 't', 'u', 'o', 'w', 'j', 's', 'r', 'm', 'n', 'a', 'f', 'z', 'z', 'x', 'z', 'y', 'h', 'u', 'm', 't',
                    'm', 'h', 'y', 'a', 'g', 'u', 'z', 'l', 't', 'q', 'z', 'm', 'n', 'p', 'i', 'w', 'h', 'z', 'k', 'v',
                    'z', 'p', 'w', 'b', 'p', 'x', 'b', 'w', 'u', 'n', 'r', 'g', 'w', 'p', 'i', 'd', 'j', 'h', 'o', 'd',
                    'y', 'q', 'r', 'l', 'f', 'a', 'j', 'p', 'z' },
                { 'v', 'k', 'b', 'l', 'i', 'e', 'c', 'g', 'f', 'a', 'a', 'v', 'r', 'i', 'r', 'i', 'r', 'w', 'u', 'y',
                    'n', 'z', 'y', 'f', 'q', 'j', 'm', 'q', 'u', 'b', 's', 'q', 'l', 'v', 'd', 'w', 'z', 'h', 'c', 'g',
                    'j', 'e', 'b', 'c', 'm', 'v', 'k', 'd', 't', 'g', 'e', 'g', 'f', 'c', 'l', 'y', 'o', 'a', 'q', 'i',
                    'b', 'k', 'a', 'p', 'f', 'f', 'l', 'g', 'o' },
                { 'n', 'n', 'x', 't', 'o', 'b', 'f', 'l', 'm', 'j', 'f', 'u', 'n', 'l', 'a', 'r', 'z', 'y', 'f', 'z',
                    'q', 'q', 'c', 'b', 's', 'r', 'g', 'a', 'c', 'n', 'o', 'r', 'a', 'o', 'k', 'q', 'p', 'q', 'c', 'd',
                    'b', 'h', 'y', 'q', 'u', 'a', 'h', 'v', 'a', 'n', 'w', 'q', 'f', 'z', 'r', 'x', 's', 'a', 'x', 'v',
                    'n', 'o', 'o', 'p', 'c', 'z', 'h', 'r', 'r' },
                { 'l', 'x', 's', 'u', 'v', 'k', 'p', 'x', 'r', 'm', 'x', 'g', 'l', 'p', 'n', 'k', 'h', 'l', 'c', 'h',
                    'k', 'z', 'w', 'y', 'o', 'n', 'a', 'n', 'u', 'u', 'g', 'g', 'r', 'a', 'a', 'o', 'k', 'r', 'n', 'd',
                    'g', 'k', 'k', 'r', 'z', 'x', 'b', 'i', 'k', 'f', 'r', 'v', 'f', 'n', 'v', 'v', 'a', 'y', 'k', 'x',
                    'u', 'q', 'd', 'n', 'q', 'f', 'b', 'a', 'z' },
                { 'o', 'd', 'f', 'a', 'p', 'y', 'b', 'p', 'b', 'm', 'b', 'g', 'd', 'y', 'n', 'r', 'u', 'k', 't', 's',
                    'u', 'q', 'm', 'k', 'v', 'z', 'c', 'd', 'c', 'e', 'c', 's', 'k', 'j', 'u', 'b', 'h', 'x', 'q', 'k',
                    'j', 'u', 's', 'n', 's', 'i', 'g', 'm', 's', 'z', 'g', 'n', 'q', 's', 'z', 'n', 't', 'e', 'q', 'x',
                    'i', 's', 'p', 's', 'd', 'l', 'u', 'm', 'j' },
                { 'm', 'w', 's', 'g', 'p', 'h', 'z', 'x', 'n', 'n', 'r', 'p', 'u', 'g', 'f', 'o', 'g', 's', 'i', 'k',
                    'j', 'h', 'u', 'd', 'z', 'n', 'h', 'k', 'j', 'v', 't', 'v', 's', 'o', 'c', 'j', 'v', 'd', 'g', 'l',
                    'q', 'z', 'a', 'k', 'g', 'h', 'z', 'm', 'z', 'j', 'y', 'k', 'q', 's', 'q', 'r', 'h', 'z', 'c', 'q',
                    'u', 'x', 'm', 'm', 'l', 'q', 'v', 'j', 't' },
                { 'd', 'u', 'j', 'd', 'u', 'w', 'j', 'b', 'v', 'x', 'c', 'g', 'x', 'p', 'y', 'r', 'f', 'q', 'z', 'g',
                    's', 'p', 'a', 'r', 'd', 'p', 'd', 't', 'k', 'o', 'o', 'q', 'i', 'y', 't', 'e', 'u', 'e', 'h', 'r',
                    'd', 'l', 'z', 'a', 'a', 'x', 'r', 'h', 'n', 'q', 'n', 'h', 'i', 'q', 'b', 'n', 'f', 'g', 'j', 'r',
                    'u', 'x', 'h', 'e', 'x', 'c', 'i', 't', 'i' },
                { 'r', 'm', 'l', 'c', 'l', 'l', 'f', 'j', 'f', 'm', 'y', 'x', 'c', 'i', 'h', 'u', 'j', 'v', 'z', 'p',
                    'e', 'q', 'j', 'b', 'a', 'n', 'b', 'c', 'x', 'u', 'l', 'o', 'j', 'y', 's', 'u', 'm', 'x', 'f', 'r',
                    'm', 'e', 'o', 'q', 'm', 'w', 'k', 'v', 't', 'j', 'm', 'x', 'b', 'v', 'a', 'b', 'k', 'd', 'g', 'j',
                    'a', 't', 'z', 'j', 'r', 'r', 'd', 'd', 'p' },
                { 'j', 'w', 'b', 'n', 'n', 'r', 'b', 'l', 'b', 'y', 'e', 'm', 'k', 'b', 'p', 'h', 'd', 't', 't', 'h',
                    'z', 'c', 'h', 'u', 'b', 'q', 'n', 's', 'v', 'r', 'j', 'e', 'p', 'k', 't', 'c', 'd', 'w', 'n', 'g',
                    'w', 'r', 'u', 'i', 'u', 'k', 'p', 'a', 'd', 'k', 'h', 'e', 'o', 'q', 'y', 'p', 'i', 'l', 'k', 'd',
                    'e', 't', 'k', 'u', 'g', 'd', 'y', 'l', 'c' },
                { 'm', 'u', 'y', 'f', 'o', 'h', 'c', 'y', 'y', 'c', 'b', 'j', 'l', 'h', 'x', 'b', 'f', 'p', 'j', 't',
                    'b', 'm', 'x', 'u', 'y', 't', 'c', 'c', 's', 'q', 'g', 'g', 'k', 'e', 'n', 'y', 'n', 'p', 'z', 'm',
                    't', 'a', 'x', 'e', 'i', 'u', 'f', 'p', 'l', 'q', 'i', 'm', 'f', 'g', 'j', 'd', 'b', 'n', 'h', 't',
                    'd', 'n', 'b', 'p', 'u', 'p', 'o', 'h', 'g' },
                { 'n', 'v', 'a', 'p', 's', 'e', 'z', 'p', 'm', 'r', 'a', 'e', 'z', 'n', 'j', 'h', 'y', 'p', 'j', 'l',
                    'w', 'e', 'r', 'm', 'i', 'g', 'g', 'z', 'w', 'p', 'f', 'l', 'l', 'h', 'b', 'd', 'm', 'c', 's', 'a',
                    't', 'v', 'e', 'v', 'k', 'q', 'c', 'i', 'f', 'n', 'v', 'd', 'u', 'm', 'p', 'c', 'v', 'x', 'b', 'r',
                    'n', 'i', 'f', 'y', 'q', 'g', 'd', 'e', 'k' },
                { 'y', 'g', 'e', 't', 'm', 'z', 'f', 'c', 'd', 'n', 'j', 'r', 'k', 'n', 'n', 'z', 'c', 'p', 'w', 'c',
                    's', 'n', 'p', 'a', 'u', 'p', 's', 'c', 's', 'w', 'n', 's', 'e', 't', 'l', 'r', 'u', 'q', 't', 'x',
                    'f', 'd', 'q', 's', 's', 'd', 'r', 'w', 'u', 'n', 'y', 'm', 'c', 'p', 'p', 'x', 'e', 'h', 'z', 'z',
                    'g', 'o', 'r', 'k', 'h', 'f', 'b', 'b', 'v' },
                { 'x', 'b', 'd', 'a', 'r', 'x', 'u', 'v', 'o', 'q', 'p', 'd', 'r', 'e', 'h', 'g', 't', 'g', 'l', 'a',
                    'i', 'm', 'i', 'w', 'd', 't', 'e', 'i', 'u', 'h', 'g', 'r', 'i', 'l', 't', 'a', 'i', 'p', 'x', 'y',
                    'g', 'o', 'd', 'z', 'u', 'k', 'f', 'n', 't', 's', 'q', 'b', 'e', 'y', 'x', 'k', 't', 'd', 's', 'q',
                    'n', 'a', 'h', 'v', 'l', 'd', 'x', 't', 's' },
                { 'w', 't', 'a', 'l', 'w', 'z', 'h', 'j', 'h', 'v', 'c', 'z', 'n', 'd', 'g', 'n', 'c', 'q', 'j', 'g',
                    'i', 'z', 'v', 'j', 'i', 'q', 'w', 'l', 'o', 's', 'g', 'm', 'l', 'i', 'x', 'k', 'k', 'h', 't', 'r',
                    'e', 'v', 's', 'r', 'a', 'y', 'g', 'c', 'o', 'p', 'k', 'z', 'q', 'f', 'k', 'z', 'y', 'i', 'm', 'm',
                    'a', 's', 'y', 'm', 'd', 'y', 'w', 'n', 'h' },
                { 'r', 'e', 'l', 'm', 'w', 'e', 'o', 'x', 'k', 'q', 'n', 'c', 'd', 'm', 's', 'k', 'y', 't', 'i', 'h',
                    'g', 'w', 'h', 'a', 'x', 'v', 'd', 'x', 't', 'q', 'e', 'k', 'w', 'p', 'y', 'v', 'v', 'o', 's', 'f',
                    'h', 'f', 'j', 'k', 'u', 'e', 'u', 'u', 'x', 'f', 'b', 'd', 'b', 'l', 'e', 'a', 'i', 'j', 'x', 'e',
                    'a', 'd', 'q', 'y', 'u', 'p', 't', 'p', 'd' },
                { 'n', 'v', 'm', 'v', 'g', 'w', 'p', 'k', 't', 'l', 'k', 'a', 'p', 'n', 'b', 'c', 't', 'e', 'k', 'd',
                    'b', 'o', 'f', 'h', 'f', 'd', 'b', 'w', 'z', 'r', 'b', 'm', 'o', 'o', 'h', 'u', 'm', 'y', 'h', 'h',
                    'k', 'r', 'h', 'z', 'g', 'l', 'd', 'a', 'p', 'n', 'f', 's', 'e', 'k', 'z', 'l', 'p', 'b', 'j', 'o',
                    'u', 'm', 'd', 'i', 'c', 'k', 'e', 'p', 'l' },
                { 'l', 'w', 'x', 'e', 'e', 'y', 'l', 'r', 'b', 'n', 'g', 'q', 's', 'a', 'u', 'c', 'a', 'h', 't', 'd',
                    'q', 'i', 'x', 'd', 'l', 'h', 'f', 'x', 'l', 'w', 'k', 'x', 'v', 'h', 'b', 'b', 'f', 'o', 's', 'i',
                    'b', 'a', 'z', 't', 'a', 'v', 'x', 'a', 'd', 'r', 'f', 'v', 'b', 'e', 'y', 'm', 'l', 'g', 'l', 'x',
                    'e', 'w', 'u', 'z', 'f', 'x', 'c', 'n', 'm' },
                { 'u', 'v', 'p', 'u', 'w', 'j', 'x', 's', 'i', 'x', 'v', 'z', 'f', 'q', 'a', 'j', 'r', 'o', 'v', 'z',
                    'c', 's', 'f', 'y', 'o', 'h', 'f', 'n', 'j', 's', 'b', 'g', 'q', 'r', 'c', 'm', 'a', 'z', 'e', 'i',
                    'x', 'b', 'k', 'e', 's', 'm', 'n', 'l', 'd', 'i', 'm', 'f', 'c', 'r', 'f', 's', 'y', 'k', 'g', 'i',
                    'f', 'h', 'o', 'v', 'y', 's', 'h', 'a', 's' },
                { 'm', 'l', 'r', 'p', 'v', 'v', 'j', 'j', 'i', 'u', 'm', 't', 'i', 'r', 'x', 'a', 'y', 'q', 'a', 'j',
                    'w', 'i', 'o', 'f', 'y', 'l', 'e', 'r', 's', 'g', 'j', 'g', 'r', 'a', 'w', 'o', 'x', 'f', 'y', 'f',
                    'c', 'k', 'a', 'k', 'e', 'y', 'm', 'c', 'q', 'n', 'n', 'o', 'x', 'd', 't', 'w', 'o', 'z', 'p', 'j',
                    'g', 'a', 'p', 'x', 'c', 'n', 'm', 'z', 't' },
                { 'm', 'g', 'x', 'w', 'j', 'h', 'c', 'j', 'u', 'f', 'z', 'j', 's', 'n', 'g', 'y', 'i', 'c', 'm', 'i',
                    't', 'v', 'q', 'v', 'n', 'n', 'z', 'a', 'b', 'a', 'v', 'n', 'j', 's', 'm', 's', 'c', 'o', 'b', 'y',
                    't', 'c', 'h', 'o', 'p', 'n', 'o', 'x', 's', 'c', 'h', 'n', 'y', 'x', 'j', 'n', 'n', 'k', 'n', 'q',
                    'l', 'l', 'e', 'u', 'd', 's', 'm', 'h', 'g' },
                { 'p', 'f', 'c', 'r', 'o', 's', 'i', 'c', 'g', 'h', 'w', 'i', 'p', 'j', 'i', 'o', 'u', 'v', 'b', 'f',
                    'l', 'u', 'q', 'w', 'y', 'k', 'b', 's', 'y', 'l', 'y', 'n', 's', 'a', 'g', 'h', 'u', 'o', 'l', 'a',
                    'v', 'h', 'l', 'm', 'q', 't', 'b', 'n', 'r', 'e', 's', 'e', 'y', 'i', 'c', 'y', 'u', 'f', 'q', 'u',
                    'q', 'r', 'j', 'j', 't', 'p', 's', 'o', 'f' },
                { 'd', 'o', 'a', 'k', 'b', 'p', 'c', 'v', 'q', 'p', 'o', 'w', 'j', 'u', 'x', 't', 'w', 'v', 'p', 'b',
                    'o', 'j', 'u', 'f', 'u', 'd', 'y', 'j', 'v', 'm', 'q', 'a', 'd', 't', 'k', 'e', 'i', 'o', 'b', 'a',
                    'g', 'r', 'w', 'p', 'l', 't', 'l', 'h', 'r', 'a', 'l', 'h', 'k', 'f', 'm', 'g', 'k', 'm', 'q', 'h',
                    'z', 'i', 'h', 'e', 'b', 't', 'k', 'j', 'j' },
                { 'o', 'j', 'r', 'f', 'i', 'h', 't', 'd', 'u', 'a', 'w', 'u', 'n', 'd', 'g', 'u', 'p', 'n', 'e', 'e',
                    'f', 'n', 'd', 'n', 'w', 'j', 'p', 'p', 't', 'a', 'b', 'h', 'm', 's', 'p', 'u', 'b', 'i', 'z', 'v',
                    'k', 'w', 's', 'y', 'b', 'y', 's', 't', 'n', 'z', 'x', 's', 'o', 'c', 'i', 'l', 'l', 'z', 'c', 'e',
                    'z', 'd', 'o', 'n', 'w', 'd', 'j', 'z', 'l' },
                { 'j', 'v', 'v', 'h', 'n', 'v', 'k', 'n', 'q', 'd', 'b', 'p', 'a', 'v', 'd', 'e', 'f', 'o', 'p', 'g',
                    'r', 'w', 'i', 'w', 'm', 'v', 's', 'p', 'f', 's', 'c', 'q', 'p', 'z', 'z', 'e', 'v', 'j', 'r', 'l',
                    'n', 'u', 'c', 'p', 's', 'f', 'u', 'x', 'w', 'j', 'e', 'p', 'h', 'm', 'l', 't', 'j', 'g', 'k', 'o',
                    'a', 'm', 'g', 'p', 'm', 'f', 't', 'j', 'p' },
                { 'm', 'u', 'c', 'h', 'w', 't', 'z', 'd', 'n', 'y', 'b', 'z', 'e', 'q', 'g', 's', 'e', 'c', 'c', 'k',
                    'm', 's', 'k', 'z', 'z', 'b', 'n', 'e', 'u', 'w', 'v', 'g', 's', 'z', 'p', 'o', 't', 'o', 't', 'i',
                    'p', 'v', 'h', 't', 'n', 'q', 'o', 'r', 's', 'q', 'd', 'e', 'k', 'p', 'd', 'l', 'q', 's', 'q', 'k',
                    'o', 'n', 't', 'g', 'n', 'i', 'w', 'g', 'z' },
                { 's', 'q', 'o', 'n', 'y', 'j', 'c', 'o', 'z', 'w', 'i', 'p', 'z', 'm', 'c', 'p', 's', 'n', 'h', 'k',
                    'f', 's', 'z', 't', 'n', 'h', 'i', 'v', 'e', 'q', 'w', 'w', 'g', 'm', 'l', 'e', 'y', 'p', 'u', 'x',
                    'l', 'e', 'p', 'n', 'r', 'r', 'e', 'l', 'e', 'n', 'v', 'm', 'f', 'w', 'f', 'u', 'g', 'n', 's', 'k',
                    'd', 'o', 'i', 'j', 'b', 'v', 'q', 'b', 'm' },
                { 'm', 'y', 'a', 'r', 'n', 'p', 'k', 'g', 't', 'v', 'n', 'g', 's', 'z', 'o', 'p', 'g', 'k', 'v', 't',
                    'c', 'h', 'y', 'r', 'r', 'j', 'u', 'o', 'b', 'x', 'a', 'o', 'v', 'a', 'h', 'l', 'p', 'r', 'r', 'k',
                    'o', 'e', 't', 'g', 'f', 'j', 'x', 'l', 't', 'u', 'g', 'w', 'd', 'g', 'p', 'w', 'q', 'l', 'k', 't',
                    'i', 'l', 'h', 'f', 'l', 'q', 'q', 'd', 'j' },
                { 'k', 'n', 'x', 'o', 'g', 'g', 'w', 'p', 'f', 'h', 'l', 'c', 'o', 'j', 'f', 'u', 'y', 'c', 'm', 'l',
                    'o', 'g', 'v', 'z', 'p', 'a', 'n', 'g', 't', 'q', 'r', 'd', 'f', 'r', 't', 'o', 'x', 'p', 'f', 'e',
                    'x', 'q', 'g', 'n', 'z', 'm', 'j', 'z', 'q', 'w', 'k', 'e', 'e', 'h', 'g', 't', 'i', 'v', 'b', 'b',
                    'n', 'v', 'g', 's', 'm', 'z', 'g', 'l', 'p' },
                { 'o', 'p', 'o', 'e', 'w', 'b', 'g', 'k', 'k', 'f', 'a', 'i', 's', 'g', 'o', 'b', 'o', 'k', 'j', 'j',
                    'n', 'm', 'w', 'i', 's', 'r', 'u', 'u', 'x', 'f', 'j', 'n', 'v', 'x', 'u', 't', 'a', 'a', 'd', 'm',
                    'h', 'f', 'x', 'b', 'n', 'l', 'd', 'c', 'v', 'o', 'n', 'j', 'd', 'k', 'r', 'x', 'b', 'o', 'r', 'a',
                    'v', 'c', 'o', 's', 'b', 'i', 'l', 'b', 'k' },
                { 'q', 'q', 'r', 'v', 'n', 'v', 'j', 'y', 'y', 'n', 'u', 'o', 'a', 'f', 'r', 'm', 'w', 'p', 'p', 'm',
                    'g', 'q', 'i', 'j', 'g', 'a', 'k', 'q', 'o', 'o', 'c', 'e', 'e', 'v', 'c', 'r', 'q', 'n', 'r', 'q',
                    'a', 'l', 'f', 'c', 's', 'w', 'p', 'p', 'n', 'e', 'd', 'w', 'w', 'l', 'f', 'e', 'o', 'r', 'w', 'e',
                    'f', 'y', 'i', 'l', 'u', 'k', 'c', 'k', 'x' },
                { 'u', 'd', 'z', 'h', 'i', 'c', 'a', 'g', 't', 'r', 'w', 'z', 'u', 's', 'y', 'i', 'x', 'e', 'y', 'q',
                    'b', 'c', 'y', 'b', 'm', 'j', 'v', 'z', 'o', 'i', 'y', 'i', 'l', 'a', 'r', 'v', 'e', 't', 'd', 'x',
                    'k', 'z', 'y', 'h', 'r', 'y', 'r', 'q', 'd', 'r', 'j', 'g', 'v', 'h', 'h', 'h', 'q', 'd', 'i', 'e',
                    'n', 'j', 'o', 'a', 'j', 'i', 'x', 'n', 'b' },
                { 'a', 'm', 'm', 'c', 'k', 'v', 'v', 'j', 'm', 'm', 'o', 'd', 'x', 'u', 'y', 'e', 'b', 'h', 'w', 'g',
                    's', 'b', 't', 'b', 'r', 'v', 'k', 'z', 's', 'z', 'd', 't', 'l', 'p', 'x', 'x', 'm', 's', 'i', 'a',
                    'g', 'w', 'f', 'd', 's', 'd', 'j', 'u', 'm', 'g', 'c', 'e', 'j', 'y', 'h', 'a', 't', 't', 'c', 'o',
                    's', 'f', 'j', 'f', 'w', 'g', 'd', 'i', 'y' },
                { 'n', 'k', 'h', 'm', 'p', 'k', 'e', 'u', 'u', 'a', 'g', 'a', 'f', 'n', 'j', 'd', 'w', 'l', 'y', 'q',
                    'n', 'm', 'i', 'u', 'v', 'q', 'q', 'd', 't', 'a', 'c', 'i', 'k', 'j', 'u', 'b', 'v', 'b', 'v', 'r',
                    'b', 'e', 'r', 'i', 'r', 'c', 'l', 'n', 'q', 'm', 'f', 'f', 'y', 'o', 'a', 'w', 'e', 's', 'z', 'z',
                    'v', 'd', 'j', 'h', 'o', 'e', 'j', 'm', 'h' },
                { 'e', 'd', 'i', 'k', 'x', 't', 'b', 'z', 'e', 'r', 'r', 's', 'w', 'x', 't', 'm', 'z', 'p', 's', 'r',
                    'q', 't', 'o', 'w', 'd', 'w', 'm', 'j', 'h', 'y', 'q', 'n', 'c', 'a', 'y', 'b', 't', 'b', 'c', 'a',
                    'u', 'u', 's', 't', 'r', 'n', 'h', 's', 'e', 'a', 'l', 'x', 'v', 'a', 't', 'a', 'y', 'h', 'l', 'h',
                    'g', 'd', 'u', 'k', 'e', 's', 'l', 'z', 'w' },
                { 'n', 'b', 'q', 'j', 'w', 'j', 'c', 'j', 'r', 'u', 'o', 't', 'g', 'l', 'q', 'i', 'g', 'r', 'i', 'n',
                    'e', 'p', 'v', 'i', 'j', 'h', 'o', 'e', 'u', 'n', 'a', 'i', 'r', 's', 't', 'n', 'c', 'w', 'y', 'v',
                    's', 'o', 'q', 'a', 'b', 'g', 'i', 'h', 'z', 's', 'x', 'e', 'h', 'u', 'o', 't', 'c', 'c', 'x', 'w',
                    'r', 'z', 'g', 'i', 'r', 'a', 'x', 'v', 'y' },
                { 'y', 'q', 'q', 'm', 'g', 'r', 'o', 'p', 'b', 'x', 'o', 'u', 'u', 'u', 'b', 'p', 'i', 'w', 'r', 'k',
                    't', 'p', 'c', 'u', 'w', 'm', 'm', 'y', 'k', 'j', 'w', 'i', 'a', 'o', 'w', 'i', 'f', 'k', 'x', 'j',
                    'i', 'o', 'd', 'e', 'i', 'g', 't', 'r', 'd', 'm', 'b', 'y', 'c', 'f', 't', 'a', 's', 'h', 'y', 'e',
                    'q', 'w', 'o', 's', 'k', 'k', 'd', 's', 'v' },
                { 'a', 'b', 'f', 'o', 'g', 'j', 'z', 'm', 'f', 'q', 'p', 'r', 'r', 'o', 'v', 'z', 'j', 'x', 'r', 'q',
                    'v', 'v', 'i', 't', 'j', 'b', 'g', 'v', 'e', 'y', 's', 'g', 'b', 'x', 'x', 'h', 'j', 'w', 't', 'o',
                    'm', 'l', 'h', 'f', 'b', 'd', 'e', 'k', 'a', 'x', 'c', 'y', 's', 'k', 't', 'd', 'n', 'z', 'b', 'r',
                    'z', 't', 'a', 'a', 'r', 'x', 'h', 'c', 'v' },
                { 'd', 'q', 'j', 'q', 'x', 'o', 'r', 'c', 'v', 'd', 'd', 's', 'h', 'd', 'n', 'r', 'w', 's', 'f', 'w',
                    't', 'y', 'x', 'n', 'a', 'y', 'g', 'x', 'h', 'i', 'u', 'm', 'y', 'd', 'c', 'x', 's', 't', 'a', 'p',
                    'y', 'f', 'h', 'f', 'i', 'w', 'z', 'g', 'p', 'g', 'c', 'i', 'g', 'a', 'x', 'h', 'a', 'd', 'g', 'h',
                    'n', 'b', 'w', 'n', 'e', 'y', 'l', 'y', 'u' },
                { 'n', 'n', 's', 's', 'x', 'a', 'c', 't', 'z', 'i', 'k', 'f', 'n', 't', 'n', 'p', 's', 'u', 'p', 'w',
                    'b', 'y', 'l', 'c', 'u', 'z', 'i', 'v', 'm', 'h', 'p', 'z', 'w', 'j', 't', 't', 'j', 'v', 'p', 'k',
                    'f', 'z', 'r', 's', 'u', 'f', 'h', 'n', 'z', 'y', 'l', 'c', 'z', 'w', 'e', 't', 'x', 'p', 'o', 'j',
                    'w', 'f', 'k', 'u', 'p', 'f', 'o', 'a', 'a' },
                { 'f', 'l', 'i', 'e', 'c', 'a', 'z', 'h', 'k', 'o', 'j', 'i', 'z', 'l', 'h', 'v', 's', 'd', 'v', 'j',
                    't', 'e', 'f', 'z', 'r', 'b', 'q', 'w', 'r', 'q', 'z', 'w', 'b', 'h', 'b', 'g', 'h', 'c', 'p', 't',
                    'q', 'a', 'c', 'r', 'm', 'j', 'o', 'g', 'o', 'j', 'p', 'i', 'q', 'w', 'j', 'h', 'x', 'z', 'd', 'p',
                    'p', 'e', 'n', 't', 'l', 'o', 'z', 'v', 's' },
                { 'q', 'o', 'k', 'r', 's', 'b', 'f', 'c', 'q', 'l', 's', 'b', 'c', 'a', 'r', 'a', 'j', 'y', 'z', 'i',
                    'e', 'o', 'a', 'i', 'e', 't', 'w', 's', 'u', 'r', 'n', 'k', 'h', 'x', 'd', 'a', 'b', 'i', 'e', 't',
                    'v', 'w', 'u', 'z', 'z', 'm', 'z', 'i', 'm', 'z', 't', 'q', 'p', 't', 'b', 't', 'o', 'x', 'o', 'i',
                    'q', 'd', 'u', 'x', 'c', 'a', 'z', 'd', 'i' },
                { 'd', 'y', 'g', 'c', 't', 'f', 'b', 'h', 'h', 'j', 't', 'g', 'e', 'm', 'x', 'x', 'n', 't', 'n', 'k',
                    'j', 'x', 'c', 'm', 's', 'b', 'q', 's', 'b', 'u', 'c', 'g', 'u', 'i', 'i', 'n', 'q', 'j', 'u', 'x',
                    'v', 'q', 'f', 'z', 'c', 'c', 'z', 'r', 'x', 'm', 'd', 'i', 'k', 'f', 'u', 'e', 'g', 'n', 'y', 'h',
                    'h', 'c', 'q', 'b', 'l', 'y', 'r', 'd', 'k' } };

        Assertions.assertFalse(demo.exist(board2, "afdfghjhy"));

        char[][] board3 =
            { { 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a',
                'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a' },
                { 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a',
                    'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a' },
                { 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a',
                    'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a' },
                { 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a',
                    'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a' },
                { 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a',
                    'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a' },
                { 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a',
                    'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a' },
                { 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a',
                    'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a' },
                { 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a',
                    'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a' },
                { 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a',
                    'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a' },
                { 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a',
                    'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a' },
                { 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a',
                    'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a' },
                { 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a',
                    'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a' },
                { 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a',
                    'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a' },
                { 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a',
                    'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a' },
                { 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a',
                    'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a' },
                { 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a',
                    'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a' },
                { 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a',
                    'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a' },
                { 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a',
                    'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a' },
                { 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a',
                    'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a' },
                { 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a',
                    'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a' },
                { 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a',
                    'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a' },
                { 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a',
                    'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a' },
                { 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a',
                    'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a' },
                { 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a',
                    'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a' },
                { 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a',
                    'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a' },
                { 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a',
                    'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a' },
                { 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a',
                    'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a' },
                { 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a',
                    'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a' },
                { 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a',
                    'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a' },
                { 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a',
                    'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'a', 'b' } };
        String longWord =
            "baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";

        Assertions.assertTrue(demo.exist(board3, longWord));
    }

    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0
            || word == null || word.length() == 0) { return false; }

        int row = board.length;
        int col = board[0].length;
        boolean[][] visited = new boolean[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (dfs(board, visited, "", word, i, j)) {
                    return true;
                }
            }
        }

        return false;
    }

    // DFS + 回溯 + 剪枝
    public boolean dfs(char[][] board, boolean[][] visited, String str, String word, int x, int y) {
        // 数组越界，扫描退出
        if (x < 0 || x >= board.length || y < 0 || y >= board[0].length) { return false; }
        if (str.length() > word.length()) return false;
        if (!word.startsWith(str)) return false;
        // 已扫描过，则退出
        if (visited[x][y]) return false;

        // 拼接字符串，然后在字典树中查找，如果找到 word，添加到目标 list
        // visited[x][y] 已被扫描过，置为 true
        str += board[x][y];
        // if (!trie.startsWith(str)) return false;
        if (word.equals(str)) return true;
        visited[x][y] = true;

        // 基于当前位置，向四个方向展开 DFS 搜索
        boolean flag = dfs(board, visited, str, word, x + 1, y)
            || dfs(board, visited, str, word, x - 1, y)
            || dfs(board, visited, str, word, x, y + 1)
            || dfs(board, visited, str, word, x, y - 1);
        if (flag) return true;

        // // 重置 visited[x][y] 为 false
        visited[x][y] = false;
        return false;
    }

}
